"""
奇周期平方根

  所有的平方根写成如下连分数表示时都是周期性重复的：

根号N=A0+1/(A1+1/(A2+1/(A3+...)))

例如，计算√23：
√23=4+√23-4=4+1/(1/(√23-4))=4+1/(1+(√23-3)/7)



  如果继续计算下去，可得到如下的展开：



整个过程可以总结如下：



从上面式子，不难看出序列正在重复。将其简记为√23 = [4;(1,3,1,8)]，表示在此之后(1,3,1,8)无限循环。
  前10个(无理数)平方根的连分数表示是：
√2=[1;(2)]，周期=1
√3=[1;(1,2)]，周期=2
√5=[2;(4)]，周期=1
√6=[2;(2,4)]，周期=2
√7=[2;(1,1,1,4)]，周期=4
√8=[2;(1,4)]，周期=2
√10=[3;(6)]，周期=1
√11=[3;(3,6)]，周期=2
√12= [3;(2,6)]，周期=2
√13=[3;(1,1,1,1,6)]，周期=5
在N ≤ 13中，恰好有4个连分数(斜体)表示的周期是奇数。
  在N ≤ 10000中，有多少个连分数表示的周期是奇数。

"""
import math
def not_com_square(n):
    if (int(n**0.5))**2==n:
        return False
    else:
        return True

def yuefen(a,b):
    max_num=1
    for i in range(2,min(int(a),int(b))+1):
        if a%i==0 and b%i==0 and i>max_num:
            max_num=i
    return max_num
        
def calculate(m):
    gh=m**0.5
    a=int(gh)
    fz=1
    fzz=1
    fmm=gh-a
    result=fzz/fmm
    l=[]
    while True:
        if yuefen(fz,m-a**2)==1:
            up=a*fz
            down=m-a**2
        elif fz==m-a**2:
            up=a
            down=1
        else:
            up=int(fz/yuefen(fz,m-a**2)*a)
            down=int((m-a**2)/yuefen(fz,m-a**2))
        print(up)
        print(down)
        mid=int(result)                     #1 3 1 8
        result=1/(result-mid)
        if down==1 or (m**0.5+up)<down:
            break
        elif [up,down] not in l:
            l.append([up,down])
        else:
            break
        a=math.fabs(a-mid*down)             #3 3 4 4
        fz=down                             #7 2 7 1
    # return len(l)   

    #     up=yuefen(a*fz,m-a**2)[0]          #4 7 3 4 4
    #     down=yuefen(a*fz,m-a**2)[1]        #7 2 7 1 7
    #     mid=int(result)                     #1 3 1 8
    #     result=1/(result-mid)
    #     if [up,down] not in l:
    #         l.append([up,down])
    #     else:
    #         break
    #     a=math.fabs(a-mid*down)             #3 3 4 4
    #     fz=down                             #7 2 7 1
    # return len(l)
# for i in range(2,14):
print(calculate(166))

# cnt=0
# for num in range(1,10001):
#     if not_com_square(num):
#         if calculate(num)%2==1:
#             print(num)
# print(cnt)





# #定义函数
# def Get(number):
#     #计算平方根
#     dd=number**0.5
#     #取整，确定开始值
#     start=int(dd)
#     #存储值、和周期值
#     peilist=[[start],[]]
#     #存储每一次的中间过程
#     middle=[]
#     #第一个中间过程
#     fenzi=1
#     sfenmu=number
#     sign=-start
#     first=[fenzi,sfenmu,sign]
#     while first not in middle:
#         middle.append(first)
#         hhd=middle[-1][1]-middle[-1][2]**2#分母
#         #分子总系数
#         fenziall=middle[-1][0]*(start-middle[-1][2])
#         #值
#         num=int(fenziall/hhd)
#         peilist[-1].append(num)
#         #周期值
#         fenzi=int(hhd/middle[-1][0])
#         sfenmu=number
#         sign=int((-middle[-1][2])-fenzi*num)
#         first=[fenzi,sfenmu,sign]
#     return number,peilist #返回值和周期值
# #开始计算
# count=0
# for i in range(1,10001):
#     ss=i**0.5
#     if int(ss)-ss!=0:
#         dd=Get(i)
#         if len(dd[-1][-1])%2==1:
#             count+=1
# print(count)
# 答案：1322